package net.freebytes.test;

public class KmpMatcher {
	private int[] failure;
	private int matchPoint;
	private byte[] bytePattern;

	int indexOf(byte[] text, int startIndex) {
		int j = 0;
		if (!verifyParas(text, startIndex)) {
			return -1;
		}
		for (int i = startIndex; i < text.length; i++) {
			while (j > 0 && bytePattern[j] != text[i]) {
				j = failure[j - 1];
			}
			if (bytePattern[j] == text[i]) {
				j++;
			}
			if (j == bytePattern.length) {
				matchPoint = i - bytePattern.length + 1;
				return matchPoint;
			}
		}
		return -1;
	}

	int lastIndexOf(byte[] text, int startIndex) {
		matchPoint = -1;
		int j = 0;
		if (!verifyParas(text, startIndex)) {
			return -1;
		}
		int end = text.length;
		for (int i = startIndex; i < end; i++) {
			while (j > 0 && bytePattern[j] != text[i]) {
				j = failure[j - 1];
			}
			if (bytePattern[j] == text[i]) {
				j++;
			}
			if (j == bytePattern.length) {
				matchPoint = i - bytePattern.length + 1;
				if ((text.length - i) > bytePattern.length) {
					j = 0;
					continue;
				}
				return matchPoint;
			}
			if (startIndex != 0 && i + 1 == end) {
				end = startIndex;
				i = -1;
				startIndex = 0;
			}
		}
		return matchPoint;
	}

	private boolean verifyParas(byte[] text, int startIndex) {
		if (text == null || text.length == 0 || startIndex > text.length) {
			return false;
		}
		return true;
	}

	int lastIndexOfWithNoLoop(byte[] text, int startIndex) {
		if (!verifyParas(text, startIndex)) {
			return -1;
		}
		matchPoint = -1;
		int j = 0;
		for (int i = startIndex; i < text.length; i++) {
			while (j > 0 && bytePattern[j] != text[i]) {
				j = failure[j - 1];
			}
			if (bytePattern[j] == text[i]) {
				j++;
			}
			if (j == bytePattern.length) {
				matchPoint = i - bytePattern.length + 1;
				if ((text.length - i) > bytePattern.length) {
					j = 0;
					continue;
				}
				return matchPoint;
			}
		}
		return matchPoint;
	}

	void computeFailure4Byte(byte[] patternStr) {
		if (patternStr == null)
			return;
		bytePattern = patternStr;
		int j = 0;
		int len = bytePattern.length;
		failure = new int[len];
		for (int i = 1; i < len; i++) {
			while (j > 0 && bytePattern[j] != bytePattern[i]) {
				j = failure[j - 1];
			}
			if (bytePattern[j] == bytePattern[i]) {
				j++;
			}
			failure[i] = j;
		}
	}
}
